#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }
    
    int lenA = 0, lenB = 0;
    struct ListNode *nodeA = headA, *nodeB = headB;
    
    while(nodeA != NULL) {
        nodeA = nodeA->next;
        lenA++;
    }
    while(nodeB != NULL) {
        nodeB = nodeB->next;
        lenB++;
    }
    
    int i = lenA - lenB;
    nodeA = headA;
    nodeB = headB;
    if (lenA < lenB) {
        i = lenB - lenA;
        nodeA = headB;
        nodeB = headA;
    }
    for (; i > 0; i--) {
        printf("nodeA[%d], val[%d]\n", i, nodeA->val);
        nodeA = nodeA->next;
    }
    
    while(nodeA != NULL && nodeB != NULL) {
        if (nodeA == nodeB) {
            return nodeA;
        }
        nodeA = nodeA->next;
        nodeB = nodeB->next;
    }
    return NULL;
}

int main() {
    struct ListNode *headA = (struct ListNode*)malloc(sizeof(struct ListNode));
    headA->val = 1;
    headA->next = NULL;

    struct ListNode *headB = (struct ListNode*)malloc(sizeof(struct ListNode));
    headB->val = 2;
    for (int i = 0; i < 10; i++) {
        headB->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        headB->val = i;
        headB = headB->next;
    }
    headB->next = NULL;

    struct ListNode *head = getIntersectionNode(headA, headB);
    printf("head: %p\n", head);
    free(headA);
    free(headB);
}